package com.example.javabasic.suanfa.剑指offer.重建二叉树;

import com.example.javabasic.mianshi.fuzhulei.TreeNode;

import java.util.*;

/**
 * @description 重建二叉树
 * @Author Lin FuYuan
 * @date 2021/7/5
 */
public class Solution {
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public static void main(String[] args) {
        int[] pre =  {1,2,4,7,3,5,6,8};
        int[] in = {4,7,2,1,5,3,8,6};
        Solution solution = new Solution();
        TreeNode treeNode = solution.reConstructBinaryTree(pre, in);
        System.out.println(treeNode);
        Queue<TreeNode> queue = new LinkedList<>();

    }



    /**
     * 构建二叉树
     *
     * @param pre 前序遍历序列
     * @param in  中序遍历序列
     * @return com.example.javabasic.suanfa.剑指offer.重建二叉树.Solution.TreeNode
     * @author Lin FuYuan
     * @date 2021/7/5
     */
    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        if (pre.length == 0) {
            return null;
        }

        if (pre.length == 1) {
            return new TreeNode(pre[0]);
        }
        //根节点值
        int root = pre[0];
        TreeNode roots = new TreeNode(root);
        int rootIndex = 0;
        //找出根节点在中序遍历的位置
        for (int i = 0; i < in.length; i++) {
            if (in[i] == pre[0]) {
                rootIndex = i;
            }
        }
        //根节点下标为0;  根据rootindex 可以得出 pre数组 左子节点为  1至 rootIndex+1;  右子节点为剩余部分
        //1>比如  前序数组为 {1,2,4,7,3,5,6,8};  中序数组为 {4,7,2,1,5,3,8,6};  根据前序数组  的值 1为root节点, 根据root节点, 算出root在中序数组中下标为 3;中序 元素1左边有三个数,
        // 那么  前序 去除 root节点1  往后三个数(2,4,7)为左子节点,剩余的则是右子节点;
        //2>
        int[] leftpre = Arrays.copyOfRange(pre, 1, rootIndex + 1);
        int[] leftin = Arrays.copyOfRange(in, 0, rootIndex );
        TreeNode left = reConstructBinaryTree(leftpre, leftin);

        int[] rightPre = Arrays.copyOfRange(pre, rootIndex + 1, pre.length);
        int[] rightIn = Arrays.copyOfRange(in, rootIndex + 1, in.length);
        TreeNode right = reConstructBinaryTree(rightPre,rightIn );
        roots.left = left;
        roots.right = right;
        return roots;
    }
}
